package 我的Java学习_算法基础.day_08;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @date 2021/8/24 - 08 - 24 - 10:35
 * @Description: 我的Java学习.day_08
 * @Version: 1.0
 */
public class _129_乘船问题 {
    /**
     * Input:
     * 10 10
     * 1 2 3 4 5 6 7 8 9 10
     * Output
     * 6
     *
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int person = sc.nextInt();
        int limit = sc.nextInt();
        int[] weights = new int[person];
        for (int i = 0; i < person; i++) {
            weights[i]= sc.nextInt();
        }
        Arrays.sort(weights);
        int countOfBoat = minBoat(weights,limit);
        System.out.println(countOfBoat);
    }

    /**
     * 思路：
     * 每次考虑最轻最重两人，若未超重，则一起过，超重则最重的单独过
     * @param weights 从小到大的体重数组
     * @param limit 船限重
     * @return 载上所有人的最少船数
     */
    private static int minBoat(int[] weights,int limit){
        int l = 0,r = weights.length-1;
        int person = weights.length;
        int countOfBoat = 0;
        while (person>0){
            if(weights[l]+weights[r]>limit){
                r--;
                person--;
                countOfBoat++;
            }else{
                r--;
                l++;
                person-=2;
                countOfBoat++;
            }
        }
        return countOfBoat;
    }
}
